package com.wtgroup.demo.面试题.我的面试;

/**
 * Aelf 区块链
 *
 * @author nisus
 * @version 0.1
 * @since 2023/6/7 15:44
 */
public class Q_求峰值 {


    /**
     * 峰值元素是指其值严格大于左右相邻值的元素。
     *
     * 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     *
     * 你可以假设 nums[-1] = nums = -∞ 。
     *
     * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题
     *
     * [-∞, 1, 10, 1, 6, 3, 5, 2, 1, -∞]
     * 2, 6
     *
     * 1, 1, 10
     * ans = 10
     * 1, 6, 10
     * ans = 10
     * 3, 10
     *
     * 注: nums[i] != nums[i+1]
     *
     */

    int solution(int[] nums) {
        int l = 0, r = nums.length - 1;
        int mid = l + (r-l) / 2;
        int currMaxIx = mid;
        while (l <= r) {
            int tmp = 0;
            // 左中右取最大
            if (nums[l] > nums[r]) {
                tmp = nums[l] > nums[mid] ? l : mid;
                r = mid-1;
            } else {
                tmp = nums[r] > nums[mid] ? r : mid;
                l = mid+1;
            }

            if (nums[tmp] > nums[currMaxIx]) {
                currMaxIx = tmp;
            }
        }

        return currMaxIx;
    }





}
